package ACWing.SearchAndGraphTheory.DFS;
//129. 火车进栈

import java.util.*;

/**
 * @author :chenjie
 * @date :Created 2022/12/19 11:08
 */
public class TrainIntoStack {
    static int stack1=1;
    static Stack<Integer> stack2=new Stack<>();//表示进站顺序
    static Stack<Integer> stack3=new Stack<>();//表示出栈顺序

    static int n;
    static int count=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();

        dfs();

    }
    public static void dfs(){//暴力搜索+回溯-
        if(count==20){
            return;
        }
        if(stack3.size()==n){
            count++;
            for (int i = 0; i < stack3.size(); i++) {
                System.out.print(stack3.get(i));

            }
            System.out.println();
        }
        if(stack2.size()!=0){
            Integer pop = stack2.pop();
            stack3.push(pop);
            dfs();
            stack2.push(pop);
            stack3.pop();
        }
        if(stack1<=n){
            stack2.push(stack1);
            stack1++;
            dfs();
            stack1--;
            stack2.pop();
        }
    }
}
